1. Technical Field
This invention relates in general to computer graphics display systems, and more particularly, to an improved method and processor for drawing one of a concave polygon, self-intersecting polygon and polygon with polygonal hole, to a graphics display means including a frame buffer for storing individual pixels for each of a plurality of lines to be displayed on a display monitor.
2. Description of the Prior Art
As is well known, computer graphics display systems are computer systems which generate and display graphic images on a raster scan display device. Such graphic images are derived from digital data stored in the system's memory. The data is typically stored in the form of points in a two or three-dimensional coordinate system, wherein the points correspond to the vertices of polygons, such as triangles. The polygons form the "building blocks" of larger objects which are the ultimate display objects. Also stored with the vertex data are parametric values, i.e., intensity, or other values that permit computation of intensity such as surface color, surface reflectivity, transparency, light sources, and normal vectors.
For a given object, this data is stored in the form of a list of instructions, called a "display list". To convert such a display list to an actual image on a raster scan display, a display processor is provided which reads the list from memory, processes the data and then writes raw pixel data to the frame buffer. In raster scan real time the frame buffer is read, and the resulting data stream is converted to an analog video signal which is sent to the display device.
The present invention relates to the functions provided in the display processor portion of such computer graphics systems. Specifically, the invention relates to the generation of data relating to a third parametric value for all pixel values of a displayed triangle, based on the position of the pixels and on other data relating to the third parameter. For example, in the so-called shading problem, shading information for a given triangle may be provided to the display processor in the form of light intensity of the vertices of the triangle. Alternatively, the display processor may be provided the parameters of the object surface, the surface orientation, and the specified light model. The display processor must then, for each pixel associated with the triangle, compute a light intensity value based on the values provided.
A special case of the shading problem exists where the polygon to be shaded comprises a concave polygon, a self-intersecting polygon or a polygon with a polygonal hole (collectively referred to herein as "concave polygons"). The problem of concave polygon shading has been treated in two principal ways, namely: (1) decomposition of the polygon into convex pieces; and (2) use of a scan-line algorithm.
In the first approach, each convex piece definitive of the decomposed polygon is shaded independently. This technique is described in "Triangulating a Simple Polygon," by M.R. Garey et al., Information Processing letters, (June 1978), pp. 175-179. Another example is described in "Surface Triangulation for Picture Production," by B. Wordenweber, IEEE CG&A (November, 1983), pp. 45-51. The major disadvantage of this technique is the reduced system performance experienced due to an increase in processing time, especially when no additional vertices are introduced during the decomposition procedure. If the generation of additional vertices is allowed, a linear-time behavior for the number of vertices can be obtained. However, the process is still time consuming. An example of this alternative approach is discussed in "A Linear-Time Algorithm for Triangulating Simple Polygons," by R.E. Tarjan and C.J. Van Wyk, PROC Eighteenth Annual ACM Symposium on Theory of Computing (1986) pp. 380-388. Also, the introduction of additional vertices should be avoided if the edge of the original polygon is split into two or more pieces. Because of round-off errors, the line equation of the pieces can differ from the equation of the original edge. This can cause problems on the visibility of a line coincidence with the original polygon edge if the application chose to draw it.
The second approach to shading concave polygons, use of a scan line algorithm, is explained in Fundamentals of Interactive Computer Graphics by J.D. Foley and A. Van Dam, at pp. 456-460 (1985). The principle disadvantage of this approach is the additional processing required in sorting of the edge list, and the computation of the slopes (dZ/dX,dR/dX,dG/dX,dB/dX) for each span of the polygon being shaded.
The present invention is designed to solve the described performance problems associated with prior art concave polygon processing approaches and provides a drawing (i.e., filling or shading) technique for concave polygons which advantageously uses much of the hardware already standard for processing convex polygons.